#pragma once
#include<iostream>
#include<vector>
using namespace std;
namespace celia
{
	template<class V>
	struct KeyofV
	{
		size_t& operator()(const V& data)
		{
			return (size_t)data;
		}
	};
	template<>
	struct KeyofV<string>
	{
		size_t operator()(const string& data)
		{
			size_t i = 0;
			for (int j = 0; j < data.size(); j++)
			{
				i += data[j] + 131;
			}
			return i;
		}
	};
	enum State
	{
		EXIST,
		EMPTY,
		DELETE
	};
	template<class K, class V>
	struct HashNode
	{
		pair<K, V> _kv;
		State _state = EMPTY;
	};
	template<class K, class V, class Hash = KeyofV<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
		inline unsigned long __stl_next_prime(unsigned long n)
		{
			static const int __stl_num_primes = 28;
			static const unsigned long __stl_prime_list[__stl_num_primes] = {
				53, 97, 193, 389, 769,
				1543, 3079, 6151, 12289, 24593,
				49157, 98317, 196613, 393241, 786433,
				1572869, 3145739, 6291469, 12582917, 25165843,
				50331653, 100663319, 201326611, 402653189, 805306457,
				1610612741, 3221225473, 4294967291
			};
			const unsigned long* first = __stl_prime_list;
			const unsigned long* last = __stl_prime_list + __stl_num_primes;
			const unsigned long* pos = lower_bound(first, last, n);
			return pos == last ? *(last - 1) : *pos;
		}
	public:
		HashTable()
			:_v(__stl_next_prime(0))
			,_n(0)
		{}
		bool Insert(const pair<K, V>& data)
		{
			if (Find(data.first))
				return false;
			Hash hash;
			if (_n * 10 / _v.size() >= 7)
			{
				HashTable<K, V> newht;
				newht._v.resize(__stl_next_prime(_v.size() + 1));
				for (auto& x : _v)
				{
					if (x._state == EXIST)
					{
						newht.Insert(x._kv);
					}
				}
				_v.swap(newht._v);
			}
			int hash0 = hash(data.first) % _v.size();
			int hashi = hash0;
			int i = 1;
			while (_v[hashi]._state == EXIST)
			{
				hashi = (hashi + i) % _v.size();
				i++;
			}
			_v[hashi]._kv = data;
			_v[hashi]._state = EXIST;
			_n++;
			return true;
		}
		bool Erase(const K& key)
		{
			Node* ret = Find(key);
			if (ret)
			{
				ret->_state = DELETE;
				_n--;
				return true;
			}
			return false;
		}
		Node* Find(const K& key)
		{
			Hash hash;
			int hash0 = hash(key) % _v.size();
			int hashi = hash0;
			int i = 1;
			while (_v[hashi]._state != EMPTY)
			{
				if (_v[hashi]._state == EXIST && _v[hashi]._kv.first == key)
				{
					return &_v[hashi];
				}
				hashi = (hashi + i) % _v.size();
				i++;
			}
			return nullptr;
		}
	private:
		vector<Node> _v;
		size_t _n;
	};
}